package com.lw.leetcode.dp.c;

import com.lw.test.util.Utils;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * LCP 57. 打地鼠
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/15 16:07
 */
public class GetMaximumNumber {

    public static void main(String[] args) {
        GetMaximumNumber test = new GetMaximumNumber();

        // 2
//        int[][] moles = {{1, 1, 0}, {2, 0, 1}, {4, 2, 2}};

        // 3
//        int[][] moles = {{2, 0, 2}, {5, 2, 0}, {4, 1, 0}, {1, 2, 1}, {3, 0, 2}};

        // 0
//        int[][] moles = {{0, 1, 0}, {0, 0, 1}};

        // 0
//        int[][] moles = {{0, 1, 0}, {0, 0, 1}, {0, 2, 1}, {0, 1, 2}, {0, 0, 2}, {1, 2, 2}};

        //
        int[][] moles = Utils.getArr(100000, 3, 0, 3);
        Set<Long> set = new HashSet<>();
        for (int[] mole : moles) {
            mole[0] = (int) (Math.random() * 10000000);
            long t = (long) mole[0] * 9 + mole[1] * 3 + mole[2];
            while (set.contains(t)) {
                mole[0] = (int) (Math.random() * 10000000);
                t = (long) mole[0] * 9 + mole[1] * 3 + mole[2];
            }
            set.add(t);
        }
        Utils.toPrint(moles);

        int maximumNumber = test.getMaximumNumber(moles);
        System.out.println(maximumNumber);
    }

    public int getMaximumNumber(int[][] moles) {
        Arrays.sort(moles, (a, b) -> Integer.compare(a[0], b[0]));
        int a = 3;
        int b = 3;
        int c = 5;
        long[][][] arr = new long[a][b][c];
        for (long[][] longs : arr) {
            for (long[] aLong : longs) {
                Arrays.fill(aLong, -1);
            }
        }
        arr[1][1][0] = 0;
        int max = 0;
        for (int[] mole : moles) {
            int t = mole[0];
            int x = mole[1];
            int y = mole[2];
            int min = 0;
            for (int i = 0; i < a; i++) {
                for (int j = 0; j < b; j++) {
                    for (int k = 0; k < c; k++) {
                        if (arr[i][j][k] == -1) {
                            continue;
                        }
                        long l = arr[i][j][k];
                        int t1 = (int) (l >> 32);
                        int c1 = (int) l;
                        int s = Math.abs(i - x) + Math.abs(j - y);
                        if (s <= t - t1) {
                            min = Math.max(min, c1 + 1);
                        }
                    }
                }
            }
            if (min == 0) {
                continue;
            }
            boolean f = true;
            for (int i = 0; i < c; i++) {
                if (arr[x][y][i] == -1) {
                    f = false;
                    arr[x][y][i] = ((long) t << 32) + min;
                    break;
                }
            }
            if (f) {
                System.arraycopy(arr[x][y], 1, arr[x][y], 0, c - 1);
                arr[x][y][c - 1] = ((long) t << 32) + min;
            }
            max = Math.max(max, min);
        }
        return max;
    }

}
